/**
 * 402. 移掉 K 位数字
 * https://leetcode-cn.com/problems/remove-k-digits/
 */

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
function removeKdigits(num, k) {
  if (k === num.length) {
    return '0';
  }
  const len = num.length - k;
  const stack = new Array(num.length).fill(' ');
  let top = -1;
  for (let i = 0; i < num.length; i += 1) {
    while (top >= 0 && num[i] < stack[top] && k) {
      top -= 1;
      k -= 1;
    }
    top += 1;
    if (top >= stack.length) {
      break;
    }
    stack[top] = num[i];
  }
  let validStart = 0;
  while (validStart < len && stack[validStart] === '0') {
    validStart += 1;
  }
  if (validStart >= len) {
    return '0';
  }
  return stack.slice(validStart, len).join('') || '0';
}

console.log(removeKdigits('987654321', 1) === '87654321');
console.log(removeKdigits('123456789', 1) === '12345678');
console.log(removeKdigits('987654321', 8) === '1');
console.log(removeKdigits('123456789', 8) === '1');
console.log(removeKdigits('1432219', 3) === '1219');
console.log(removeKdigits('10200', 1) === '200');
console.log(removeKdigits('10', 2) === '0');
console.log(removeKdigits('10', 1) === '0');
console.log(removeKdigits('10001', 1) === '1');
console.log(removeKdigits('1234567890', 9) === '0');
